
//用数组实现栈
class Stack {
    private int[] arr;
    private int top;
    private int size;
    public Stack(int n) {
        arr = new int[n];
        top = 0;
        size = n;
    }
    //栈是否为空
    public boolean isEmpty() {
        return top == 0 ? true : false;
    }
    //判断栈是否已满
    public boolean isFull(){
        return top == size ? true : false;
    }
    //进栈
    public void push(int data) {
        if(!isFull()) {
            arr[top++] = data;
        }else {
            System.out.println("栈已满，入栈错误");
        }
    }
    //出栈
    public int pop() {
        if(!isEmpty()){
            return arr[--top];
        } else {
            System.out.println("栈已空,出栈错误");
            return -1;
        }
    }
    //获取栈顶元素
    public int getTop(){
        if(!isEmpty()) {
            return arr[top];
        }else {
            System.out.println("栈为空,无栈顶元素");
            return -1;
        }
    }
    //当前数量
    public int getSize(){
        return top;
    }
}

//用数组实现队列
class Queue {
    private int[] arr;
    private int head;
    private int tail;
    private int size;
    public Queue(int n) {
        arr = new int[n];
        head = 0;
        tail = 0;
        size = n;
    }

    //判断是否为空
    public boolean isEmpty() {
        return head == tail ? true : false;
    }
    //判断是否已满
    public boolean isFull() {
        return tail == size ? true : false;
    }
    //入队列
    public void enQueue(int data) {
        if(!isFull()) {
            arr[tail++] = data;
        }else {
            System.out.println("队列已满,入队出错");
        }
    }

    //出队列
    public int deQueue() {
        if(!isEmpty()) {
            return arr[head++];
        }else {
            System.out.println("队列为空，出队出错");
            return -1;
        }
    }
    //返回尾元素
    public int getTail() {
        if(!isEmpty()) {
            return arr[tail-1];
        }else {
            System.out.println("队列为空，出队出错");
            return -1;
        }
    }

    //返回头元素
    public int getHead() {
        if(!isEmpty()) {
            return arr[head];
        }else {
            System.out.println("队列为空，出队出错");
            return -1;
        }
    }

    //返回元素个数
    public int size() {
        return tail - head;
    }
}

//用数组实现循环队列
class CircularQueue {
    private int[] arr;
    private int head;
    private int tail;
    private int size;
    private int limit;

    public CircularQueue(int n) {
        arr = new int[n];
        head = tail = size = 0;
        limit = n;
    }

    //判断是否为空
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }
    //判断是否已满
    public boolean isFull() {
        return size == limit ? true : false;
    }
    //入队
    public void enQueue(int data) {
        if(!isFull()) {
            arr[tail++] = data;
            if(tail == limit){
                tail = 0;
            }
            ++size;
        }else {
            System.out.println("队列已满,入队错误");
        }
    }
    //出队
    public int deQueue() {
        if(!isEmpty()) {
            int temp = arr[head++];
            if(head == limit ){
                head = 0;
            }
            --size;
            return temp;
        }else {
            System.out.println("队列已空,出队错误");
            return -1;
        }
    }
    //返回数量
    public int getSize() {
        return size;
    }
    //返回队头元素
    public int getHead() {
        return arr[head];
    }
    //返回队尾元素
    public int getTail() {
        return arr[tail-1];
    }
}

public class StackQueueCircularQueue {
    public static void main(String[] args) {
        //创建一个栈
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(3);
        stack.push(4);
        while(!stack.isEmpty()){
            System.out.print(stack.pop() + " ");
        }
        System.out.println();

        //创建一个队列
        Queue queue = new Queue(5);
        queue.enQueue(9);
        queue.enQueue(1);
        queue.enQueue(1);
        while (!queue.isEmpty()) {
            System.out.print(queue.deQueue() + " ");
        }
        System.out.println();

        //创建一个循环队列
        CircularQueue cq = new CircularQueue(5);
        cq.enQueue(1);//入队
        cq.enQueue(2);
        cq.enQueue(3);

        cq.deQueue();//出队
        cq.deQueue();

        cq.enQueue(4);//入队
        cq.enQueue(5);
        cq.enQueue(6);
        cq.enQueue(7);

        while (!cq.isEmpty()) {
            System.out.print(cq.deQueue() + " ");
        }
    }
}
